import Queue from "./Queue";
import Comparator, {compareTo} from "../utils/Comparator";
import Obj, {equalsTo} from "../core/Obj";
import FullCapacityException from "../exceptions/FullCapacityException";
import IllegalArgumentException from "../exceptions/IllegalArgumentException";
import Collections from "../utils/Collections";
import {hashArray} from "../core/Hash";

const className = "priorityQueue";

/**
 * 基于优先级堆的无界优先级队列。优先级队列的元素根据它们的自然排序{@link defaultComparator}排序，或者根据队列构造时提供的
 * {@link Comparator} 排序。
 *
 * 该队列的头部是相对于指定排序的最小的元素。如果多个元素被绑定为最小值，则头部是这些元素中的一个。队列查看、删除操作都基于队列头部的元素。
 *
 * 每个PriorityQueue实例都有一个容量。容量是用于存储队列中元素的数组的大小。它始终不小于队列大小。当元素添加到PriorityQueue时，它的大小会自动
 * 增长但容量不会增长，但您可以手动增加它。
 *
 * @param E 需要存入此队列的元素类型
 * @see Queue
 * @version 1.0
 */
export default class PriorityQueue<E> extends Obj implements Queue<E> {

  /**
   * 一个数组的容器，用于存储元素。
   *
   * @private
   * @version 1.0
   */
  private readonly _elements: E[];

  /**
   * 此队列可以存储的元素数量。
   *
   * @private
   * @version 1.0
   */
  private _capacity: number;

  /**
   * 此队列的比较器。
   *
   * @private
   * @version 1.0
   */
  private readonly _comparator: Comparator | undefined;

  /**
   * 构造一个具有默认元素、容量和比较器的 PriorityQueue。
   *
   * 如果您不提供默认元素，它将不包含任何内容。
   * 如果您不提供默认容量，它会将容量设置为无限。
   * 如果您不提供默认比较器，它将使用自然比较器。
   *
   * @param elements 需要默认置入此队列的元素
   * @param capacity 此队列的容量
   * @param comparator 此队列的比较器
   * @throws {FullCapacityException} 这个队列无法容纳这些元素
   * @throws {IllegalArgumentException} 这个容量数字不正确
   * @version 1.0
   */
  public constructor(elements: E[] = [], capacity: number = -1, comparator?: Comparator) {
    super();

    if (capacity !== -1 && elements.length > capacity) {
      throw new FullCapacityException(className, capacity);
    }

    if (capacity < -1) {
      throw new IllegalArgumentException("capacity should be bigger than -1");
    }

    this._elements = [];
    this._capacity = capacity;
    this._comparator = comparator;

    if (elements !== undefined) {
      for (let element of elements) {
        this.offer(element, this._comparator);
      }
    }
  }

  [Symbol.iterator](): Iterator<E> {
    return this.iterator();
  }

  /**
   * 尝试将指定的元素加入到列表中。
   *
   * 若列表因该元素的加入发生了变化，则返回true。
   *
   * @param e 需要加入到集合中的元素
   * @return {boolean} 若列表因该元素的加入发生了变化，则返回true，否则返回false
   * @throws {FullCapacityException} 列表已经满了
   * @version 1.0
   */
  public add(e: E): boolean {
    return this.offer(e);
  }

  /**
   * 返回此队列的容量。
   *
   * @return {number} 返回此队列的容量
   * @version 1.0
   */
  capacity(): number {
    return this._capacity;
  }

  /**
   * 清空此队列。
   *
   * @version 1.0
   */
  public clear(): void {
    this._elements.splice(0);
  }

  /**
   * 返回此队列是否包含指定的元素。
   *
   * @param e 需要查找的元素
   * @return {boolean} 如果此队列包含该元素，则返回true，否则返回false
   * @version 1.0
   */
  public contains(e: E): boolean {
    return this._elements.findIndex(element => equalsTo(e, element)) !== -1;
  }

  public equals(b: Obj): boolean {
    if (b instanceof PriorityQueue) {
      return Collections.equals(this, b);
    }
    return false;
  }

  /**
   * 增加此队列的容量使其可以容纳更多的元素。
   *
   * 给出的容量必须比现有的容量更大，否则将会抛出{@link IllegalArgumentException}。当容量被设定为-1时，表示此队列容量无穷大，之后将不能再增
   * 加容量，也将不再判断容量是否充满。
   *
   * @param capacity 新的容量
   * @throws {IllegalArgumentException} 新的容量比当前容量小或容量已无法增长
   */
  public grow(capacity: number) {
    if (capacity < this._capacity && capacity !== -1) {
      throw new IllegalArgumentException(
        "capacity " + capacity + " is smaller than current capacity " + this._capacity + " and is not -1");
    } else {
      this._capacity = capacity;
      return true;
    }
  }

  public hashCode(): number {
    return hashArray(this._elements);
  }

  /**
   * 返回此队列是否为空。
   *
   * @return {boolean} 如果此队列不包含任何元素，则返回true，否则返回false
   * @version 1.0
   */
  public isEmpty(): boolean {
    return this._elements.length !== 0;
  }

  /**
   * 返回此队列是否已满。
   *
   * @return {boolean} 如果此队列存储的元素已到达容量，则返回true，否则返回false。若容量为-1，则永远不会满容量
   */
  public isFull(): boolean {
    return this._elements.length === this._capacity;
  }

  /**
   * 返回由队列内所有元素组成的迭代器。
   *
   * @return {Iterator<E>} 一个由队列内所有元素组成的迭代器
   * @see Iterator
   * @version 1.0
   */
  public iterator(): Iterator<E> {
    const that = this;
    let index = 0;
    return {
      next(): IteratorResult<E> {
        return {
          value: that._elements[index++],
          done: index > that._elements.length
        };
      }
    };
  }

  /**
   * 检索但不删除此队列的头部，如果此队列为空，则返回 undefined。
   *
   * @return {E | undefined} 此队列的头部元素，若此队列为空则返回undefined
   * @version 1.0
   */
  public peek(): E | undefined {
    return this._elements.length === 0 ? undefined : this._elements[0];
  }

  /**
   * 检索并移除此队列的头部，如果此队列为空，则返回 undefined。
   *
   * @return {E | undefined} 此队列的头部元素，若此队列为空则返回undefined
   * @version 1.0
   */
  public poll(): E | undefined {
    if (this._elements.length === 0) {
      return undefined;
    } else {
      return this._elements.shift();
    }
  }

  /**
   * 移除此队列中所有与指定元素相同的元素。
   *
   * 此方法会调用{@link Obj#equals}方法进行相等判断。
   *
   * @param e 与需要从队列中被删除的元素相等的元素
   * @return {boolean} 如果有元素从队列中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public remove(e: E): boolean {
    let flag = false;
    for (let i = 0; i < this._elements.length; i++) {
      if (equalsTo(e, this._elements[i])) {
        for (let j = i; j < this._elements.length; j++) {
          this._elements[j] = this._elements[j + 1];
        }
        flag = true;
      }
    }
    return flag;
  }

  /**
   * 使用过滤器，移除此集合中所有符合过滤器要求的元素。
   *
   * @param filter 一个lambda表达式，当表达式返回true时，表示该元素符合过滤器要求
   * @return {boolean} 如果有元素从集合中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public removeIf(filter: (e: E) => boolean): boolean {
    let flag = false;
    for (let i = 0; i < this._elements.length; i++) {
      if (filter(this._elements[i])) {
        for (let j = i; j < this._elements.length; j++) {
          this._elements[j] = this._elements[j + 1];
        }
        flag = true;
      }
    }
    return flag;
  }

  /**
   * 移除此集合中第一个与指定元素相同的元素。
   *
   * 此方法会调用{@link Obj#equals}方法进行相等判断。
   *
   * @param e 与需要从集合中被删除的元素相等的元素
   * @return {boolean} 如果有元素从集合中被删除，则返回true，否则返回false
   * @version 1.0
   */
  public removeFirst(e: E): boolean {
    let flag = false;
    for (let i = 0; i < this._elements.length; i++) {
      if (equalsTo(e, this._elements[i])) {
        for (let j = i; j < this._elements.length; j++) {
          this._elements[j] = this._elements[j + 1];
        }
        flag = true;
        break;
      }
    }
    return flag;
  }

  /**
   * 返回此队列中的元素数。
   *
   * @return {number} 返回此队列中的元素数
   * @version 1.0
   */
  public size(): number {
    return this._elements.length;
  }

  /**
   * 返回由队列内所有元素组成的数组。
   *
   * 该数组内的元素会是队列中元素的<strong>浅拷贝</strong>，因此后续对队列的操作不会影响到数组的浅层，反之亦然。
   *
   * @return {E[]} 一个由集合内所有元素组成的数组
   * @version 1.0
   */
  public toArray(): E[] {
    return this._elements;
  }

  public toString(): string {
    return this._elements.toString();
  }

  private offer(e: E, comparator?: Comparator): boolean {
    if (!this.isFull()) {
      let c = comparator === undefined ? this._comparator : comparator;

      let index = 0;
      for (let i = 0; i < this._elements.length; i++) {
        if (compareTo(e, this._elements[i], c) === -1) {
          index = i;
          break;
        }
      }

      for (let i = this._elements.length - 1; i >= index; i--) {
        this._elements[i + 1] = this._elements[i];
      }
      this._elements[index] = e;

      return true;
    } else {
      throw new FullCapacityException(className, this._capacity);
    }
  }
}
